//
//  Matrix.cpp
//

#include "Matrix.h"

Matrix::Matrix() {
    graph = NULL;
    map = NULL;
    path = NULL;
}

Matrix::~Matrix() {
    if(graph) {
        delete graph;
    }
    if(map) {
        delete map;
    }
    if(path) {
        delete path;
    }
}

void Matrix::loadFromInput(vector<string> inputLines) {
    vector<string> stringsList;
    splitString(&stringsList, inputLines[0], " ");
    n = atoi(stringsList[0].c_str());
    fo = atoi(stringsList[1].c_str());
    co = atoi(stringsList[2].c_str());
    fd = atoi(stringsList[3].c_str());
    cd = atoi(stringsList[4].c_str());
    k = atoi(stringsList[5].c_str());
    
    if(map) {
        delete map;
    }
    map = new int[(n)*(n)];
    
    int currRow = 0;
    for (int i=1; i<inputLines.size(); i++) {
        vector<string> row;
        splitString(&row, inputLines[i], " ");
        for (int col=0; col<n; col++) {
            map[col+currRow*n] = atoi(row[col].c_str());
        }
        currRow++;
    }
}

void Matrix::createGraph() {
    if(graph) {
        delete graph;
    }
    
    graph = new Graph(n, n); // O(n^2)
    connectNodes(); // O(k * n^2)        
}

void Matrix::findPath() {
    if(path) {
        delete path;
    }
    path = new list<PathNode*>();
    
    Dijkstra d(graph, k); // O(1)
    Node* fromNode = graph->getNode(fo-1, co-1); // O(1)
    Node* toNode = graph->getNode(fd-1, cd-1); // O(1)
    d.findPath(fromNode, toNode);
    
    getPath(fromNode, toNode); // O(k * n^2)
    
    //cout << "camino 1: " << path->size() << endl;
}

void Matrix::connectNodes() {
    for(int row=0; row<graph->rows; row++) { // O(n)
        for(int col=0; col<graph->cols; col++) { // O(n)
            Node* node = graph->getNode(row, col); // O(1)
            if (map != NULL) {
                node->jumpPower = map[(col+row*graph->cols)];
            } else {
                node->jumpPower = rand() % graph->cols + 1;
            }
            
            for(int jumpPower=1; jumpPower<=node->jumpPower+k; jumpPower++) { // O(k)
                int powerUsed = jumpPower > node->jumpPower ? node->jumpPower : jumpPower;
                int kUsed = jumpPower > node->jumpPower ? jumpPower - node->jumpPower : 0;
                if(col < graph->cols-jumpPower) {
                    graph->connect(node, graph->getNode(row, col+jumpPower), powerUsed, kUsed); // O(1)
                }
                if(col >= jumpPower) {
                    graph->connect(node, graph->getNode(row, col-jumpPower), powerUsed, kUsed);
                }
                if(row < graph->rows-jumpPower) {
                    graph->connect(node, graph->getNode(row+jumpPower, col), powerUsed, kUsed);
                }
                if(row >= jumpPower) {
                    graph->connect(node, graph->getNode(row-jumpPower, col), powerUsed, kUsed);
                }
            }
        }
    }
}

void Matrix::getPath(Node* fromNode, Node* toNode) {
    Node* node = toNode;
    // Cargo los valores desde el nodo final saliendo con la menor cantidad de saltos.
    // Desde los otros nodos puede que la cantidad de saltos que use no sea la minima.
    int jumpsCount = node->minJumps;
    int kLeft = k;
    int lastUsedK = 0;
    int lastPowerUsed = 0;
    int totalUsedK = 0;
    // Recorro hacia atras hasta llegar al nodo inicial
    while(node != NULL && node != fromNode) { // O(n^2), a lo sumo recorro todos los nodos una vez
        Node* previousNode = NULL;
        int iKLeft;
        int kUsed = 0;
        int powerUsed = 0;
        // solo busco entre los nodos que tengan suficiente kLeft
        for(iKLeft = totalUsedK; iKLeft<=k; iKLeft++) { // O(k)
            if(node->jumpsSoFar[iKLeft] == jumpsCount) {
                previousNode = node->prevNodes[iKLeft]->toNode;
                kUsed = node->prevNodes[iKLeft]->kUsed;
                powerUsed = node->prevNodes[iKLeft]->powerUsed;
                break;
            }
        }
        if(previousNode) {
            jumpsCount = node->jumpsSoFar[iKLeft] - 1;
            kLeft -= kUsed;
            totalUsedK += kUsed;
            path->push_front(new PathNode(node, lastPowerUsed, lastUsedK, iKLeft)); // O(1)
            
            //cout << path->front()->node->row << ", " << path->front()->node->col << " usedK: " << usedK << endl;
            
            lastUsedK = kUsed;
            lastPowerUsed = powerUsed;
            
            node = previousNode;
            
            if(node == fromNode) {
                path->push_front(new PathNode(node, powerUsed, kUsed, k));
            }
        } else {
            node = NULL;
        }
    }
}

int Matrix::checkPathOk() {
    Node* fromNode = graph->getNode(fo-1, co-1); // O(1)
    Node* toNode = graph->getNode(fd-1, cd-1); // O(1)
    Node* currNode = fromNode;
    int kLeft = k;
    
    if (path->back()->node != toNode) {
        return 3; // end error
    }
    while (path->size() > 1) {
        int powerUsed = path->front()->powerUsed;
        int kUsed = path->front()->kUsed;
        kLeft -= kUsed;
        if (kLeft < 0) {
            return 1; // k error
        }
        path->pop_front();
        PathNode* next = path->front();
        if (!((currNode->col + powerUsed + kUsed == next->node->col && currNode->row == next->node->row) ||
              (currNode->row + powerUsed + kUsed == next->node->row && currNode->col == next->node->col) ||
              (currNode->col - powerUsed - kUsed == next->node->col && currNode->row == next->node->row) ||
              (currNode->row - powerUsed - kUsed == next->node->row && currNode->col == next->node->col)))
        {
            return 2; // jump error
        }
        currNode = path->front()->node;
    }
    return 0;
}

void Matrix::splitString(vector<string>* out, string str, string delimiter) {
    unsigned long fromIndex = 0;
    unsigned long delimiterIndex = 0;
    while((delimiterIndex = str.find(delimiter, fromIndex)) != -1) {
        out->push_back(str.substr(fromIndex, delimiterIndex));
        fromIndex = delimiterIndex + delimiter.length();
    }
    out->push_back(str.substr(fromIndex, delimiterIndex));
}

bool Matrix::didFindPath() {
    if(path == NULL) {
        return false;
    }
    Node* fromNode = graph->getNode(fo-1, co-1);
    return path->size() > 0 && path->front()->node == fromNode;

}

void Matrix::printMap() {
    for (int row=0; row<graph->rows; row++) {
        vector<int> rowArr;
        for (int col = 0; col<graph->cols; col++) {
            Node* node = graph->getNode(row, col);
            cout << node->jumpPower << " ";
        }
        cout << endl;
    }
}

void Matrix::printPath(bool useTPOutputFormat) {
    if (useTPOutputFormat) {
        cout << path->size()-1 << endl;
    }
    bool isFirstNode = true;
    for (list<PathNode*>::iterator it=path->begin(); it != path->end(); it++) {
        if (useTPOutputFormat) {
            if(!isFirstNode) {
                cout << (*it)->node->row+1 << " " << (*it)->node->col+1 << " " << (*it)->kUsed << endl;
            }
            isFirstNode = false;
        } else {
            cout << "(" << (*it)->node->row+1 << "," << (*it)->node->col+1 << ", power:" <<
            (*it)->powerUsed << "/" << (*it)->node->jumpPower;
            if ((*it)->kLeft != -1) {
                cout << " {k:" << (*it)->kLeft << "/" << k << ", used:" << (*it)->kUsed <<"}";
            }
            cout << ")";
            
            if (++it != path->end()) {
                cout << " -> ";
            }
            --it;
        }
    }
}

int Matrix::getN() {
    return n;
}

int Matrix::getK() {
    return k;
}